package leetcode.Over_Four_hundred;

import java.util.HashMap;

/**
 * 回旋镖的数量
 *
 * 也是使用查找表求解
 * i 到两边的距离要相等，所以以 i 为枢纽来求解其他的点
 *
 * 使用 map 存储其他店到 i 的距离，以及该距离值出现的次数，大于 1 就有解
 *
 */
public class Test447 {
    /**
     * 相同距离出现两次，答案为 2
     * 相同距离出现三次，答案为 6，排列问题
     *
     * 计算一点和其他点之间的距离，使用哈希表存储，若同一距离出现多次，则可以形成回旋镖。
     * 假设同一距离出现 n 次，由数字规律可推出回旋镖的数量 sum = n*(n-1) 。
     * 本人开始只能做到存储到哈希表，然后按该公式累加得到最后结果。
     * 参考了速度第一的答案，优化如下：
     * 假设当前同一距离的数量为 n, 回旋镖数量为 n*(n-1),
     * 当再出现一个同一距离时，回旋镖的数量应为 (n+1)*n，与之前相差 (n+1)*n - n*(n-1) = 2*n，
     * 所以只需要把最后答案加上 2*n, 最后 n+1 再存储到哈希表中。
     *
     */

    public int numberOfBoomerangs(int[][] points) {
        int len = points.length;
        // 回旋镖的数量
        int ans = 0;
        HashMap<Double, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i != j) {
                    // 计算两点间的距离
                    double dis = Math.pow(points[i][0] - points[j][0], 2)
                            + Math.pow(points[i][1] - points[j][1], 2);
                    // 首次加入距离，并初始化
                    if (!map.containsKey(dis)) {
                        map.put(dis, 1);
                    } else {
                        // 再次发现该距离，则距离的值要加 1
                        int n = map.get(dis);
                        map.put(dis, 1 + n);
                        // 同时回旋镖的个数累加 2*n 个
                        ans += 2 * n;
                    }
                }
            }
            map.clear();
        }
        return ans;
    }
}
